package com.nowc.week.w101_ak;

import java.io.*;
import java.util.*;

public class f {
    // 快速幂：计算 a^e mod m
    private static long modPow(long a, long e, int m) {
        long r = 1 % m;
        a %= m;
        while (e > 0) {
            if ((e & 1) != 0) r = (r * a) % m;
            a = (a * a) % m;
            e >>= 1;
        }
        return r;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 读入 base, c0, mod
        StringTokenizer st = new StringTokenizer(br.readLine());
        long base = Long.parseLong(st.nextToken());
        long c0   = Long.parseLong(st.nextToken());
        int mod   = Integer.parseInt(st.nextToken());

        // 读入所有查询
        int q = Integer.parseInt(br.readLine());
        long[] K = new long[q];
        for (int i = 0; i < q; i++) {
            K[i] = Long.parseLong(br.readLine());
        }

        // 特判 mod==1
        if (mod == 1) {
            for (int i = 0; i < q; i++) bw.write("0\n");
            bw.flush();
            return;
        }

        // 我们只关心 c1, c2, … 其中
        // c1 = base^c0 % mod; c2 = base^c1 % mod; …
        // 下面做周期检测：firstPos[x] = 第一次出现 x 的下标 j (1-based)，没出现为 0。
        int[] firstPos = new int[mod];
        Arrays.fill(firstPos, 0);
        List<Integer> seq = new ArrayList<>(mod+1);

        // 生成 c1
        long cur = modPow(base, c0, mod);
        int idx = 1;
        seq.add((int)cur);
        firstPos[(int)cur] = 1;

        int t = -1, L = -1, N = -1;
        // 继续生成直到在 firstPos 中再遇到
        while (true) {
            idx++;
            cur = modPow(base, cur, mod);
            int x = (int)cur;
            if (firstPos[x] != 0) {
                // 发现重复
                t = firstPos[x]; // 周期从第 t 项开始
                N = idx - 1;     // distinct 的长度
                L = N - t + 1;   // 周期长度
                break;
            }
            seq.add(x);
            firstPos[x] = idx;
        }

        // 构造前缀和 pref：pref[0]=0, pref[i]=c1+...+c_i mod mod, i=1..N
        long[] pref = new long[N+1];
        pref[0] = 0;
        for (int i = 1; i <= N; i++) {
            long s = pref[i-1] + seq.get(i-1);
            if (s >= mod) s -= mod;
            pref[i] = s;
        }

        // 前缀段和 & 周期段和
        // 前缀不包含 c_t，长度 t-1
        long sumPre    = (t > 1 ? pref[t-1] : 0);
        // 周期包括 c_t, c_{t+1}, ..., c_N
        long sumCycle  = (pref[N] - sumPre + mod) % mod;

        // 回答查询
        for (int i = 0; i < q; i++) {
            long k = K[i];
            long ans;
            if (k <= N) {
                // 直接落入前 N 项
                ans = pref[(int)k];
            } else {
                // 拆成前缀 + 完整周期*count + 余项
                long R    = k - (t - 1);        // 除去前 t-1 项后剩余要加的数量
                long full = R / L;              // 完整周期个数
                long rem  = R % L;              // 额外余下 rem 个

                ans = sumPre;
                // 注意 full 可能很大，先 mod 掉
                ans = (ans + (full % mod) * sumCycle) % mod;

                if (rem > 0) {
                    // 从 c_t 开始，加 rem 个：c_t..c_{t+rem-1}
                    int right = t - 1 + (int)rem;
                    long sumRem = (pref[right] - sumPre + mod) % mod;
                    ans = (ans + sumRem) % mod;
                }
            }
            bw.write(ans + "\n");
        }

        bw.flush();
    }
}
